'''
无向图的桥判定法则
dfn[u] < low[v]

'''

class Tarjan:
    def __init__(self):
        return

    @staticmethod
    def check_graph(edge, n):
        # edge: 边连接关系 [[],..] n:节点数

        # 访问序号与根节点序号
        dfn = [0] * n
        low = [0] * n
        # 割点
        cut_node = []
        bridge = []

        # 中间变量
        stack = []
        index = 1
        in_stack = [0] * n

        def tarjan(i, father):
            nonlocal index
            dfn[i] = low[i] = index
            index += 1
            stack.append(i)

            in_stack[i] = 1
            child = 0
            for j in edge[i]:
                if j != father:
                    if not dfn[j]:
                        child += 1
                        tarjan(j, i)
                        x, y = low[i], low[j]
                        low[i] = x if x < y else y
                        # 两种情况下才为割点 low[i] <= dfn[i]
                        if father != -1 and dfn[i] <= low[j]:
                            cut_node.append(i)
                        elif father == -1 and child >= 2:
                            cut_node.append(i)
                    elif in_stack[j]:
                        x, y = low[i], dfn[j]
                        low[i] = x if x < y else y
            return

        for k in range(n):
            if not dfn[k]:
                tarjan(k, -1)
        return cut_node